package org.usmile.algorithms.learn.graph.dfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ConnectedComponent1 {
    @SuppressWarnings("unchecked")
    public List<Integer>[] components(Graph graph) {
        if (graph == null) {
            return new ArrayList[0];
        }

        int ccCount = 0;
        int[] visited = new int[graph.getV()];
        for (int v = 0; v < graph.getV(); v++) {
            if (visited[v] == 0) {
                ccCount++;
                dfs(graph, v, ccCount, visited);
            }
        }

        List<Integer>[] result = new ArrayList[ccCount];
        for (int v = 0; v < graph.getV(); v++) {
            int ccId = visited[v];
            if (result[ccId - 1] == null) {
                result[ccId - 1] = new ArrayList<>();
            }

            result[ccId - 1].add(v);
        }

        return result;
    }

    private void dfs(Graph graph, int v, int ccId, int[] visited) {
        visited[v] = ccId;
        for (int w : graph.adj(v)) {
            if (visited[w] == 0) {
                dfs(graph, w, ccId, visited);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);

        System.out.println(Arrays.toString(new ConnectedComponent1().components(graph)));
    }
}
